﻿using System;

namespace QSharp.Scheme.Classical.Sequential
{
    public static class Heap
    {
        public interface IHeapNode
        {
        }

        public interface IHeap
        {
            IHeapNode SwapUp(IHeapNode a, IHeapNode b);
            IHeapNode SwapDown(IHeapNode a, IHeapNode b);

            IHeapNode GetParent(IHeapNode n);
            IHeapNode GetLeft(IHeapNode n);
            IHeapNode GetRight(IHeapNode n);

            IHeapNode Root { get; }
        }

        public interface IListedHeap : IHeap
        {
            IHeapNode GetLastNonLeaf();
            IHeapNode GetPrevNodeLinearly(IHeapNode n);
        }

        /**
         * <summary>
         *  To elevate a newly introduced node at the end of the heap
         * </summary>
         */
        public static void Exalt(IHeap h, IHeapNode n, Comparison<IHeapNode> cmp)
        {
            var p = h.GetParent(n);

            while (p != null)
            {
                if(cmp(p, n) >= 0)
                {
                    break;
                }
                n = h.SwapUp(p, n);
                p = h.GetParent(n);
            }
        }

        /**
         * <summary>
         *  To send an end node temporarily elevated to the root position to 
         *  a proper place. Since it's a leaf node, it's expected to be sent
         *  back to leaf level again.
         * </summary>
         */
        public static void Expel(IHeap h, IHeapNode p, Comparison<IHeapNode> cmp)
        {
            while (true)
            {
                var left = h.GetLeft(p);
                var right = h.GetRight(p);

                if (left == null && right == null)
                    return;

                if (right == null)
                {
                    if (cmp(p, left) < 0)
                        p = h.SwapDown(p, left);
                    else
                        return;
                }
                else if (left == null)
                {
                    if (cmp(p, right) < 0)
                        p = h.SwapDown(p, right);
                    else
                        return;
                }
                else if (cmp(left, right) < 0)
                {
                    if (cmp(p, right) < 0)
                        p = h.SwapDown(p, right);
                    else
                        return;
                }
                else
                {
                    if (cmp(p, left) < 0)
                        p = h.SwapDown(p, left);
                    else
                        return;
                }
            }
        }

        /**
         * <summary>
         *  Push the root down to the leaf side in preparation for a removal.
         *  It may be an express way to get a root node from a tree-based heap
         * </summary>
         */
        public static IHeapNode Relegate(IHeap h, IHeapNode d, Comparison<IHeapNode> cmp)
        {
            while (true)
            {
                var left = h.GetLeft(d);
                var right = h.GetRight(d);

                if (left == null && right == null)
                    return d;

                if (right == null)
                {
                    d = h.SwapDown(d, left);
                }
                else if (left == null)
                {
                    d = h.SwapDown(d, right);
                }
                else if (cmp(left, right) < 0)
                {
                    d = right;
                }
                else
                {
                    d = left;
                }
            }
        }
    }
}
